As background for our invention consider previous, related patents and publications. There exist several broad categories of prefetching methods. One category of prefetching methods is hardware in the cache controller or storage controller to prefetch cache lines based on the observed cache misses. For example, U.S. Pat. No. 4,807,110, issued February 1989 to Pomerene et al shows a computer system having a cache memory and a main memory. In addition to the regular cache directory, the cache contains an additional directory termed a shadow directory. This shadow directory tracks cache misses and prefetches cache lines according to the reference history by associating a given line with the next line to be accessed. This mechanism prefetches to reduce cache misses but makes no improvements to performance of cache hits. Furthermore, since prediction is based on cache line reference patterns and cache line sizes are typically 128 bytes finer reference patterns are not detected.
IBM Technical Disclosure Bulletin Vol. 34No. 2, July 1991, pp. 375-376 "Cache Prefetching Scheme with Increased Timeliness and Conditional Prefetches for a Two-Level Cache Structure" by Ignatowski et al describes a prefetch scheme in which a cache miss results in a prefetch of the next sequential line address. While processing the prefetch, the processor may generate a miss on a demand fetch, i.e., not a prefetch. This cancels the prefetch so that the demand fetch can be handled. This technique reduces bus and memory system contention. A prefetched line, when it is actually referenced results in a "pseudo-miss" which initiates another prefetch, as if there had been a miss. This mechanism is located within the storage controller and responds only to cache misses. As before, there is no improvement in the cache hit case and large line sizes mask detailed reference patterns.
IBM Technical Disclosure Bulletin Vol. 34No. 2, July 1991, pp. 371-372 "Algorithm for Non-Sequential Cache Prefetching" by Ignatowski et al describes a prefetch scheme for non-sequential cache prefetching located in the storage controller. A table is maintained indexed by the address of a cache miss. The table contains the address of the next miss to occur. In this way pairs of related misses are formed. At a later time, when the first of the pair causes a cache miss, the second is prefetched. To be effective, the table size must be much larger than the cache directory. The two misses may be totally unrelated, therefore the subsequent sequence of misses may not be the same. Also, this does not improve the performance of cache hits.
Another broad category of prefetching is to add new instructions specifying when the hardware should prefetch. For example a paper "Software Prefetching" by Callahan et al was published in the Proceedings of the Fourth International Conference on Architectural Support For Programming Languages and Operating Systems in April 1991. New instructions are added to the processor's instruction set. These prefetch instructions behave like load instructions except no data are actually loaded into the processor. The cache directory is checked and if there is a miss, the requested line is prefetched. The implementation of the instruction could be to prefetch as described, or less expensive implementations may choose to ignore the prefetch instruction. Some time after the prefetch instruction is issued, a normal load instruction requests the data transfer, but if the line containing the data had already been loaded into the cache, the cache miss is avoided. This technique requires that the programs run on a computer system must be modified, something that is not always possible to do. The compiler has to insert prefetch instructions into the program, which may not be possible in all instances.
Another broad class of prefetching is instruction prefetching based on branch prediction. There have been many proposed schemes for prefetching instructions. Since instruction access patterns are more regular than data access patterns, prediction-based prefetching of instructions is much more common than prefetching data. For example, U.S. Pat. No. 4,943,908 issued July 1990 to Emma et al and U.S. Pat. No. 4,691,277 issued September 1987 to Kronstadt et al describe means where a table containing branch history is used to prefetch instructions. Branch instructions and instruction prefetching have fundamental differences with Load instructions and data prefetching. For branch prediction, the primary problem is determining if the branch is taken or not; if this is predicted correctly, the address of the next instruction is generally very easy to determine. For Load instructions, there is no conditional action to take into account; however, the address of the data fetch changes frequently. The prefetch of Branch instructions does not modify the processor's registers, but a Load instruction does modify the processor's registers. Therefore, branch prediction and instruction prefetch techniques are generally not applicable to load prediction and data prefetching.